/**
 * Written By: MinHo Kim (minho.kim.korea@gmail.com)
 * Copyright (C) 2011, MinHo Kim, Software Expert Program, KAIST University, Seoul, Korea.
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published 
 * by the Free Software Foundation; version 2 of the License.
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; 
 * without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
 * See the GNU General Public License for more details.
 */
package kaist.sep502.tsp.controller;

import kaist.sep502.tsp.algorithm.heuristic.Heuristic;
import kaist.sep502.tsp.model.CityPath;
import kaist.sep502.tsp.model.Problem;

/**
 * @author minho kim
 *
 */
public class GreedySearch extends SearchAlgorithm {

	/* (non-Javadoc)
	 * @see kaist.sep502.tsp.controller.SearchAlgorithm#search()
	 */
	@Override
	public Solution search() {
		solution.expandedNodeCount = 0;
		solution.startStopWatch();
		
		CityPath cityPath = new CityPath();
		cityPath.set(Problem.getDepartureCityNo(), 0.0);
		int departureCityNo = Problem.getDeparture().getCityNo();
		int currentCityNo = departureCityNo;
		Heuristic h = new Heuristic();
		
		do {
			solution.expandedNodeCount++;
			currentCityNo = Problem.getClosestCityNo(currentCityNo, cityPath.tourHistory);
			
			if(currentCityNo == -1){ // if it can't find the closest city, it means it travled all cities.
				currentCityNo = 0;
			}
			
			h = heuristicAlgorithm.getHx(cityPath, currentCityNo);
			cityPath.set(h.cityNo, h.hx);
		} while(currentCityNo != departureCityNo);
		
		solution.setSuccess(true);
		solution.startStopWatch();
		solution.setGoalCityPath(cityPath);
		
		return solution;
	}
}
